package com.example.num;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个整数数组nums,从数组中找出两个满足相加之和等于目标数target。
 * 假设每个输入只有一个唯一的答案，而且不可以重复使用相同的元素。
 * 将两个数的下标值存放到数组内返回。
 */
public class TwoNum {

    // 暴力破解
    /*
    private static int[] twoSum(int[] nums, int target) {
        int[] arr = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    arr[0] = i;
                    arr[1] = j; 
                }
            }
        }
        return arr;
    }
     */
    // 标记位
    private static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] arr = new int[]{-1, -1};// 找不到就返回[-1,-1]
        for (int i = 0; i < nums.length; i++) {
            // target减去当前值nums[i]然后判断map中是否存在该值，如果存在就是找到了
            if (map.containsKey(target - nums[i])) {
                arr[0] = map.get(target - nums[i]);
                arr[1] = i;
            }
            map.put(nums[i], i);
        }
        return arr;
    }

    /**
     * 二分查找法
     * 先根据i值获取target - i,再利用二分查找在后续元素中查找target - i的值
     * @param nums 数组
     * @param target 目标数
     */
    private static int[] binaryTwoSum(int[] nums, int target) {
        Arrays.sort(nums);// 将数组调整为升序排列
        int[] arr = new int[]{-1, -1};// 找不到就返回[-1,-1]
        for (int i = 0; i < nums.length; i++) {
            int j = binarySearch(nums, i + 1, target - nums[i]);
            if (j != -1) {
                arr[0] = i;
                arr[1] = j;
                break;
            }
        }
        return arr;
    }

    private static int binarySearch(int[] nums,int index, int target) {
        int left = index, right = nums.length - 1;// 左右指针
        int mid = (left + right) / 2;// 中间指针
        while (left <= right) {
            if (target > nums[mid]) {
                left = mid + 1;
                mid = (left + right) / 2;
            } else if (target < nums[mid]) {
                right = mid - 1;
                mid = (left + right) / 2;
            } else {
                return mid;
            }
        }
        return -1;// 找不到这个值
    }

    public static void main(String[] args) {

        // [1, 3, 4, 6, 10]   11 -----> [0, 4]
        System.out.println(Arrays.toString(twoSum(new int[]{1, 3, 4, 6, 10}, 11)));
        // [1, 2, 3, 4, 5, 6, 7, 8, 9]   13 -----> [3,8]
        System.out.println(Arrays.toString(binaryTwoSum(new int[]{5, 3, 7, 4, 1, 2, 9, 6, 8}, 13)));

    }

}
